home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / mphf / search.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  7.2 KB  |  220 lines
  1. /********************************  search.c  *********************************
  2.  
  3.   Purpose:    Implement the searching stage of the MPHF algorithm.
  4.  
  5.   Provenance:    Written and tested by Q. Chen and E. Fox, March 1991.
  6.           Edited and tested by S. Wartik, April 1991.
  7.  
  8.   Notes:    The other two stages must have been performed already.
  9. **/
  10.  
  11. #include <stdio.h>
  12.  
  13. #include "types.h"
  14. #include "pmrandom.h"
  15. #include "support.h"
  16.  
  17. #ifdef __STDC__
  18.  
  19. extern int    fit_pattern( arcsType* arcs, verticesType* vertices, int i,
  20.                 char* disk, intSetType *primes, intSetType* slotSet );
  21. extern void    initialize_search( arcsType* arcs, verticesType* vertices, char* disk );
  22. extern void    initialize_primes( int n, intSetType* primes );
  23.  
  24. #else
  25.  
  26. extern int    fit_pattern();
  27. extern void    initialize_search();
  28. extern void    initialize_primes();
  29.  
  30. #endif
  31.  
  32.  
  33. /*************************************************************************
  34.  
  35.     searching( arcsType*, verticesType* )
  36.  
  37.   Return:    int -- NORM on success, ABNORM on failure.
  38.  
  39.   Purpose:    Search a MPHF for the key set.
  40.  
  41.   Notes:    The "prec" field is used as the "vertex visited" marker.
  42.  
  43.           The slotSet variable actually is only used in fit_pattern().
  44.         However, since storage for it must be dynamically allocated,
  45.         and since this routine calls fit_pattern() repeatedly,
  46.         it's declared here, where storage can be allocated just once.
  47. **/
  48.  
  49. int searching( arcs, vertices )
  50.     arcsType        *arcs;
  51.     verticesType    *vertices;
  52. {
  53.     int        i,                      /* Each vertex in the VS list.         */
  54.         searching_tries = 0,    /* Running count of searching tries.    */
  55.         status = ABNORM;        /* Condition variable.                */
  56.     char    *disk;                  /* Simulated hash table.                */
  57.     intSetType    primes,                /* Table of primes for pattern shifts.    */
  58.         slotSet;               /* Set of hash addresses.        */
  59.  
  60.     disk = (char*) owncalloc( arcs->no_arcs, sizeof(char) );
  61.     slotSet.intSetRep = (int*) owncalloc( vertices->maxDegree, sizeof(int) );
  62.     initialize_primes( arcs->no_arcs, &primes );
  63.  
  64.     while ( (searching_tries++ < SEARCHINGS) && (status == ABNORM) ) {
  65.     status = NORM;
  66.     i = vertices->vsHead;            /* Get the highest-level vertex. */
  67.     initialize_search( arcs, vertices, disk );
  68.  
  69.     while ( i != NP ) {    /* Fit keys of level of vertex i onto the disk. */
  70.         vertices->vertexArray[i].prec = VISIT;
  71.  
  72.         if ( fit_pattern(arcs, vertices, i, disk, &primes, &slotSet) == ABNORM ) {
  73.         status = ABNORM;    /* Search failed at vertex i.  Try */
  74.         break;            /* a new pattern.           */
  75.         }
  76.         else     /* Search succeeded.  Proceed to next node. */
  77.         i = vertices->vertexArray[i].succ;
  78.     }
  79.     }
  80.  
  81.     free( disk );
  82.     free( (char *)slotSet.intSetRep );
  83.     free( (char *)primes.intSetRep );
  84.     return(status);
  85. }
  86.  
  87.  
  88.  
  89. /*************************************************************************
  90.  
  91.     fit_pattern( arcsType*, verticesType*, int, char*,
  92.             intSetType*, intSetType* )
  93.  
  94.   Return:    int -- NORM if a fit is found, ABNORM if not.
  95.  
  96.   Purpose:    Compute a pattern for a level and fit it onto the hash table.
  97.             If a pattern is found, then the g values for vertices on that
  98.         level are set appropriately, and the slots on the disk for
  99.         the vertices are filled.
  100. **/
  101.  
  102. int fit_pattern( arcs, vertices, i, disk, primes, slotSet )
  103.     arcsType        *arcs;    /* in: The arcs in the graph.            */
  104.     verticesType    *vertices;/* in out: The vertices in the graph.        */
  105.     int            i;        /* in: Vertex's location in vertex-selected list. */
  106.     char        *disk;    /* in out: The hash table (disk).                 */
  107.     intSetType        *primes,  /* in: Prime number table                         */
  108.             *slotSet; /* Set of slots taken by keys in this pattern.    */
  109. {
  110.     arcType *arc;               /* Current arc.                */
  111.     int        shift,            /* Shift value for the pattern.        */
  112.         side,               /* Side indicator (0 or 1).        */
  113.         hashAddress,        /* Hash address being tried.        */
  114.         fitOK = ABNORM,     /* Fit condition variable.        */
  115.         no_fits = 0;        /* Running count of attempts to fit.    */
  116.  
  117.     side = (i >= vertices->no_vertices/2);
  118.     shift = primes->intSetRep[pmrandom() % primes->count];
  119.  
  120.     while ( (no_fits++ < arcs->no_arcs) && (fitOK == ABNORM) ) {
  121.  
  122.     fitOK = NORM;
  123.     slotSet->count = 0;      /* Initialize slot set to empty.        */
  124.  
  125.     arc = vertices->vertexArray[i].first_edge;
  126.     while ( arc != 0 ) {  /* Iterate over all arcs in this level. */
  127.  
  128.         /* If the key for arc is at this level, */
  129.         /* get its hash address.            */
  130.         if ( vertices->vertexArray[arc->h12[(side+1)%2]].prec == VISIT ) {
  131.  
  132.         hashAddress = abs(arc->h0 +
  133.             vertices->vertexArray[arc->h12[0]].g +
  134.             vertices->vertexArray[arc->h12[1]].g
  135.             ) % arcs->no_arcs;
  136.  
  137.             /* See if this key can be put at hashAddress. */
  138.         if ( disk[hashAddress] != EMPTY ) {    /* Collision.  Clear    */
  139.             int    k;                /* marked slots in disk.*/
  140.             for ( k = 0; k < slotSet->count; k++ )
  141.             disk[slotSet->intSetRep[k]] = EMPTY;
  142.  
  143.             /* Try a new shift. */
  144.             vertices->vertexArray[i].g =
  145.             ( vertices->vertexArray[i].g + shift ) % arcs->no_arcs;
  146.             fitOK = ABNORM;
  147.             break;
  148.         }
  149.         else {    /* Success.  Remember the address, */
  150.               /* and mark the table.         */
  151.             slotSet->intSetRep[slotSet->count++] = hashAddress;
  152.             disk[hashAddress] = FULL;
  153.         }
  154.         } /* end of if */
  155.         arc = arc->next_edge[side];    /* Hash next arc. */
  156.     } /* end of inner while */
  157.     } /* end of outer while */
  158.     return(fitOK);
  159. }
  160.  
  161.  
  162. /*************************************************************************
  163.  
  164.     initialize_search( arcsType*, verticesType*, char* )
  165.  
  166.   Return:    void
  167.  
  168.   Purpose:    Prepare for the search stage: Put random values in all
  169.           the g fields, mark all vertices un-visited, and empty the disk.
  170. **/
  171.  
  172. void
  173. initialize_search( arcs, vertices, disk )
  174.    arcsType    *arcs;          /* in: arcs.        */
  175.    verticesType *vertices;      /* out: vertices.    */
  176.    char        *disk;          /* out: the hash table. */
  177. {
  178.    int     i;
  179.  
  180.    setseed( pmrandom() );                             /* Set the seed.        */
  181.  
  182.    for ( i = 0; i < vertices->no_vertices; i++ )  {
  183.      vertices->vertexArray[i].g = pmrandom() % arcs->no_arcs;
  184.      vertices->vertexArray[i].prec = NOTVISIT;
  185.    }
  186.                                                       /* Reset the hash table.*/
  187.    for ( i = 0; i < arcs->no_arcs; disk[i++] = EMPTY );
  188. }
  189.  
  190. /*************************************************************************
  191.  
  192.     initialize_primes( int, intSetType* )
  193.  
  194.   Return:    void
  195.  
  196.   Purpose:    Set up the prime number table.
  197. **/
  198.  
  199. void
  200. initialize_primes( n, primes )
  201.    int n;                 /* in: the size of the hash table. */
  202.    intSetType *primes;    /* out: the prime number table.     */
  203. {
  204.    int i,
  205.        testingNumber = 2;       /* Testing number for possible prime numbers.  */
  206.  
  207.    primes->intSetRep = (int*) owncalloc( PRIMES, sizeof(int) );
  208.  
  209.    primes->intSetRep[0] = 1;        /* 1 is added to the table, although it */
  210.    primes->count = 1;               /* is not a prime.                      */
  211.    while ( (testingNumber++ < n) && (primes->count < PRIMES) ) {
  212.      if ( n % testingNumber != 0 ) {                /* Get first PRIMES-1    */
  213.         for ( i = testingNumber - 1; i > 0; i-- )   /* prime numbers.        */
  214.           if ( testingNumber % i == 0 )
  215.              break;
  216.         if ( i == 1 ) primes->intSetRep[primes->count++] = testingNumber;
  217.      }  /* end of if */
  218.   }  /* end of while */
  219. }
  220.